|
In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements. ==Definition== For any set ''A'' of lines in the Euclidean plane, one can define an equivalence relation on the points of the plane according to which two points ''p'' and ''q'' are equivalent if, for every line ''l'' of ''A'', either ''p'' and ''q'' are both on ''l'' or both belong to the same open half-plane bounded by ''l''. When ''A'' is finite or locally finite〔For an arrangement to be locally finite, every bounded subset of the plane may be crossed by only finitely many lines.〕 the equivalence classes of this relation are of three types: #the interiors of bounded or unbounded convex polygons (the ''cells'' of the arrangement), the connected components of the subset of the plane not contained in any of the lines of ''A'', #open line segments and open infinite rays (the ''edges'' of the arrangement), the connected components of the points of a single line that do not belong to any other lines of ''A'', and #single points (the ''vertices'' of the arrangement), the intersections of two or more lines of ''A''. These three types of objects link together to form a cell complex covering the plane. Two arrangements are said to be ''isomorphic'' or ''combinatorially equivalent'' if there is a one-to-one adjacency-preserving correspondence between the objects in their associated cell complexes.〔, page 4.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Arrangement of lines」の詳細全文を読む スポンサード リンク
|